//
// Description: 染色法判断二分图 模板
// Created by Loading on 2022/5/22.
//

/*
 * 适用于求一个图是否为二分图，
 * 二分图：如果一个图可以将所有节点分成不相交的两个集合，且每条边的两个端点都不在同一集合中，那么这个图是二分图，否则不是二分图
 */

/*
 * 算法思想：用两种颜色将图内的所有节点染色。
 * 如果一个图是二分图，那么一个节点所连接的所有节点都与这个节点不在同一集合中，也就应该染上不同的颜色。
 * 首先将一个节点染成颜色 1，遍历它的所有邻接点 j
 * 1、如果 j 未染过色，则递归染成颜色 2
 * 2、如果 j 已染过色，则检查染过的颜色是否与当前节点一致，若一致，则冲突，染色失败，不是二分图
 *
 * 存在奇数（节点个数）环的图，一定不是二分图！
 */

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 10;

// 邻接表，无向图，边数为两倍
int h[N], e[N * 2], ne[N * 2], idx;
// 每个点的颜色，0表示未染色，1表示白色，2表示黑色
int color[N];

int n;

/* 时间复杂度：O(n + m)，n 表示点数，m 表示边数 */
// dfs 染色，将节点x染成c色，返回是否染色成功
bool dfs(int x, int c) {
    // 染色
    color[x] = c;

    // 递归 x 的相邻节点
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!color[j]) {
            // 相邻节点未染色，递归染成不同颜色
            if (!dfs(j, 3 - c)) {
                return false;
            }
        } else if (color[j] == c) {
            // 相邻节点已染色，如果和当前节点颜色一致，染色失败，不是二分图
            return false;
        }
    }

    return true;
}

int main() {

    return 0;
}